1. Field of the Invention
The present invention generally relates to a wireless communication link between handheld devices and network for accessing data and, more particularly, to a data transfer mechanism well suited for handheld devices with small memory sizes and restricted processor speeds.
2. Background Description
The past few years have seen a considerable reduction in the cost of computer systems. This coupled with the exponential decrease in size of microprocessors and memories along with rapid progress in VLSI (Very Large Scale Integrated) technology has resulted in a huge market for handheld devices. Smart-phones, palmtop computers, Personal Digital Assistants (PDAs) and automobile installed personal computers (Auto PCs) are becoming very popular. For example, one million Palm Pilots from US Robotics were sold in its first year. Orthogonal to the growth in popularity of handheld computers, Internet and networking applications have been growing at a rapid pace. The number of users who now want to remain connected even when they are mobile is growing. This, coupled with the rapid advances in wireless communication, has made it possible to browse the World Wide Web (WWW or the Web) in the Internet, check e-mail, transfer files, get information like stock quotes, flight arrival/departure information, and even do business transactions using a handheld device like a PDA.
However, the performance of current mobile applications is usually not acceptable. Traditional computing and networking paradigms do not give good performance on handheld devices communicating over a weakly connected link, e.g., a wireless link. Typical handheld devices do not have hard disks. Handheld devices typically use flash memory or battery backed Random Access Memory (RAM) to provide nonvolatile storage. Thus, traditional file systems and data access methods do not work well on handheld devices. Similarly, traditional network communication protocols like TCP/IP (Transfer Control Protocol/Internet Protocol) do not perform well on weakly connected links such as the links typifying handheld devices. It has been noted that TCP responds to all losses by invoking congestion control and avoidance algorithms, and that this results in degraded end-to-end performance in wireless and lossy systems. In addition, due to severe memory restrictions, not all handheld devices can implement the TCP/IP stack and satisfy runtime memory requirements. It is also important to realize, given the limited amount of memory and computing resources on handheld devices, that there is a need to provide a wide variety of services by having a simple integrated software structure and by eliminating functional duplication. See J. Kay and J. Pasquale, xe2x80x9cThe Importance of Non-Data Touching Processing Overheads in TCP/IPxe2x80x9d, Proceedings of SIGCOMM ""93, ACM, 1993.
There is considerable amount of work in providing a replicated, weakly consistent storage mechanism for mobile computing environments. The Coda project, described by J. J. Kistler and M. Satyanarayanan in xe2x80x9cDisconnected Operation in the Coda File Systemxe2x80x9d, ACM Transactions on Computer Systems, 10:3-25, 1992, uses optimistic concurrency control and prefetching for supporting mobile computing. It logs all updates during disconnected mode and replays the log on reconnection. Later versions of Coda introduce certain adaptive mechanisms to support low bandwidth networks and intermittent communication.
The Bayou project, described by Douglas B. Terry, Marvin M. Theimer, Karin Peterson, Alan J. Demers, Mike J. Spreitzer and Carl H. Hauser in xe2x80x9cManaging Update Conflicts in Bayou, A Weakly Connected Replicated Storage Systemxe2x80x9d, Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles, 1995, defines an architecture for sharing data among mobile users and provides methods for detection and resolution of conflicts. It implements a mechanism for enabling client application to continue even if a conflict remains.
The Rover toolkit, described by Anthony D. Joseph, Alan F. deLespinasse, Joshua A. Tauber, David K. Gifford and M. Frans Kaashoek in xe2x80x9cRover: A Toolkit for Mobile Information Accessxe2x80x9d, Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles, 1995, provides mobile communication support on the basis of relocatable dynamic objects and queued remote procedure calls. Rover allows client operation and invocation of non-blocking remote procedure calls even when a host is disconnected.
The Cadmium project, described by Aline Baggio in xe2x80x9cDesign and Early Implementation of the Cadmium Mobile and Disconnectable Middleware Supportxe2x80x9d, INRIA Research Report 3515, October 1998, uses a mechanism for referencing remote objects, a support station model, a mechanism for binding to objects and a dynamic replication, caching, and prefetching scheme to provide system level support for disconnected and mobile usage. It assumes the use of powerful laptop computers as the mobile clients.
The BNU project, described by T. Watson and B. Bershad in xe2x80x9cLocal Area Mobile Computing on Stock Hardware and Mostly Stock Softwarexe2x80x9d, Proceedings of USENIX Symposium on Mobile and Location-Independent Computing, Cambridge, Mass., 1993, is also an RPC-driven application framework that includes proxies on stationary hosts for hiding the mobility of the system. Later versions of the project also includes support for disconnected operation like the queued RPC model.
The InfoPad project described by My T. Le, Fred Burghardt, Srinivasan Seshan and Jan Rabaey in xe2x80x9cInfoNet: The Networking Infrastructure of InfoPadxe2x80x9d, Proceedings of Compcon, 1995, also has the proxy approach where the mobile device is dumb and the entire processing is offloaded to the server. They assume a permanent connection and there is no notion of disconnected operation on the client.
Xerox""s PARCTAB system, described by R. Want, B. N. Schilit, N. I. Adams, R. Gold, K. Peterson, D. Goldberg, J. R. Ellis and M. Weiser in xe2x80x9cAn Overview of the PARCTAB Ubiquitous Computing Experimentxe2x80x9d, Personal Communications, Vol. 2, No. 6, IEEE, 1995, also assumes a permanent connection and all services are off-loaded to the server by using the system""s xe2x80x9cTab Agentxe2x80x9d mechanism.
WebExpress, described by Barron C. Housel and David B. Lindquist in xe2x80x9cWebExpress: A System for Optimizing Web Browsing in a Wireless Environmentxe2x80x9d, Proceedings of the ACM/IEEE MOBICOM ""96 Conference, 1996, implements an HTML (HyperText Markup Language) cache and uses the concept of differencing as an original transfer mechanism to reduce network traffic and latency. In addition, they do HTTP (HyperText Transfer Protocol) reductions for connection overheads and verbose protocol inefficiencies.
However, most of this work in mobile computing and information access relates to operating system principles and adding weak consistency models along with caching, pre-fetching, etc., and with enabling remote procedure calls. The applicants"" invention may be seen as a layer beneath these principles and can be used effectively for improving the performance of the above systems. The protocol described herein will improve the effective data transfer rate. It has been sufficiently demonstrated in literature that TCP and other wired network protocols do not perform well for wireless networks. Some work has been done to solve this problem by proposing modifications to TCP.
Hari Balakrishnan, Venkata N. Padmanabhan, Srinivasan Seshan and Randy H. Katz, in xe2x80x9cA Comparison of Mechanisms for Improving TCP Performance over Wireless Linksxe2x80x9d, IEEE/ACM Transactions on Networking, December 1997, have a good comparison of several schemes designed to improve the performance of TCP in wireless networks. They classify these schemes into three broad categories: (1) end-to-end protocols, where loss recovery is performed by the sender; (2) link-layer protocols, that provide local reliability; and (3) split-connection protocols, that break the end-to-end connection into two parts at the base station.
Ajay Bakre and B. R. Badrinath in xe2x80x9cI-TCP: Indirect TCP for Mobile Hostsxe2x80x9d, Proceedings of the 15th International Conference on Distributed Computing Systems, May 1995, split a TCP connection so that the uplink and downlink connections can be optimized separately, and congestion control and retransmissions on the wireless link can be isolated from those on the wireline link. But this comes at the price of breaking end-to-end TCP semantics and inducing extra copying overhead.
Hari Balakrishnan, Srinivasan Seshan and Randy Katz, in xe2x80x9cImproving Reliable Transport and Handoff Performance in Cellular Wireless Networksxe2x80x9d, ACM Wireless Networks, 1(4), December 1995, propose a link-layer protocol that introduces a module, called the snoop agent, at the base station which monitors every packet that passes through the TCP connection in both directions and maintains a cache of TCP segments sent across the link that have not yet been acknowledged by the receiver. There are more such proposed modifications to TCP, but a small handheld device may not be able to implement the modified TCP protocol because it may even be larger. In addition, dynamic RAM is restricted on such devices and the buffer area for the TCP stack may become a major concern along with wasted processing power during the copying of data.
Furthermore, there has been a lot of work related to avoiding end-to-end congestion control and re-transmissions at the lower layers in the OSI (Open Systems Interconnection) layer model, e.g., designing a Medium Access Control (MAC) for Wireless Local Area Networks (LANs). See K. C. Chen, xe2x80x9cMedium Access Control of Wireless LANs for Mobile Computingxe2x80x9d, IEEE Network, September/October 1994. But, these techniques may be seen as orthogonal to the data transfer mechanism being proposed herein. The disclosed protocol will only gain from techniques that improve the raw transfer rate over wireless networks.
A group of companies has come together to propose a xe2x80x9cWireless Application Protocolxe2x80x9d (WAP). See Wireless Application Protocol Form, http://www.wapforum.org. The WAP is fast becoming the de-facto world standard for wireless information and telephony services on digital mobile phones and other wireless terminals. WAP filters HTML documents into their WML to utilize binary transmission for greater compression during web browsing where a lot of text is transmitted.
Lazaridis et al., in U.S. Pat. No. 5,802,312, present a xe2x80x9cSystem for Transmitting Data Files Between Computers in a Wireless Environment Utilizing a File Transfer Agent Executing on Host Systemxe2x80x9d. The inventions disclosed by Lazaridis et a. have similar goals, but they do not propose a communication protocol. In addition to recommending a communications protocol, the applicants seek to avoid all unnecessary data duplication. Similarly, Eggleston et al. in U.S. Pat. No. 5,771,353 propose a xe2x80x9cSystem Having Virtual Session Manager Used Sessionless-Oriented Protocol to Communicate with User Device via Wireless Channel and Session-Oriented Protocol to Communicate with Host Serverxe2x80x9d.
It is therefore an object of the present invention to provide a data transfer mechanism for handheld devices with small memory size and restricted processor speeds.
It is another object of the invention to provide a solution to the problem of re-transmissions in case of frequent network disconnections and thus save expensive bandwidth.
It is a further object of the invention to provide a data transfer mechanism for handheld devices that reduces battery power consumption.
According to the invention, there is provided a communication mechanism with an integrated software structure for handheld devices communicating over a wireless link. The communication mechanism is particularly well suited for mobile clients connected to a server over weakly connected links as it handles broken links and re-connections very well. An application on the mobile client connects to a peer application on the server through a Gateway on the server. Thus, the server applications themselves do not need to handle different standards and protocols for different clients, e.g., a WindowsCE client or a Smart-Phone client.
The system eliminates functional duplication which makes the footprint of this system small. Hence, it is well suited for handheld devices where memory is at a premium. The system is optimized to perform minimal computing and avoid unnecessary buffering and duplication of data. It is, thus, suited for handheld devices where computing power is constrained since they typically are built around slower microprocessors than desktops. The system recognizes the non-availability of a hard disk on a handheld device and ensures that buffering is not done for data access since data can now be modified xe2x80x9cin placexe2x80x9d for systems built around RAM, EEPROM, FLASH, and other similar technologies used in handheld devices.
The system allows the application to start using a data file even before receiving the entire file by using a xe2x80x9cValidity Tablexe2x80x9d that has information about the valid, i.e., usable, portions of a file. The system also allows the application to send only the modified portions of a file to the other side. This saves precious bandwidth since the entire file does not have to be re-transmitted. The system, further, helps in power conservation since it avoids unnecessary duplication of data. This is done by reducing the path length of the program and avoiding unnecessary data copying loops. Reduction in power consumption helps in increasing the battery life of the handheld device. The system provides two-way data transfer useful for file transfers, mail, Web browsing, personal information management.